package main

import (
	"fmt"
)

/*
	俄罗斯套娃信封问题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。

示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
*/

func maxEnvelopes(envelopes [][]int) int {

	//sort.Slice(envelopes,func(i,j int)bool{
	//	return  envelopes[i][0]<envelopes[j][0]
	//})

	// 快速排序
	quickSort(envelopes, 0, len(envelopes) - 1)
	// fmt.Println(envelopes)
	dp:=make([]int,len(envelopes))
	for i,_:=range dp{
		dp[i]=1
	}
	MM:=0
	for i:=0;i<len(dp);i++{

		for j:=0;j<i;j++{
			if envelopes[i][0]>envelopes[j][0]&&envelopes[i][1]>envelopes[j][1]{
				dp[i]=max(dp[i],dp[j]+1)

			}
		}
		MM=max(MM,dp[i])
	}
	return MM
}

func max(a,b int)int{
	if a>b{
		return a
	}
	return b
}

func quickSort(nums [][]int, left, right int) {
	for left >= right {
		return
	}
	val := nums[left]
	k := left
	for i := left + 1; i <= right; i ++ {
		if nums[i][0] < val[0] {   // 交换
			nums[k] = nums[i]
			nums[i] = nums[k + 1]
			k ++
		}
	}
	nums[k] = val
	quickSort(nums, left, k - 1)
	quickSort(nums, k + 1, right)
}

func main() {
	fmt.Println(maxEnvelopes([][]int{{2,100},{3,200},{4,300},{5,500},{5,400},{5,250},{6,370},{6,360},{7,380}}))
}
